package com.hdu.hot100.binarySearch;


public class lc4 {
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int len1 = nums1.length;
            int len2 = nums2.length;

            int kth1 = (len1 + len2 + 1) / 2;
            int kth2 = (len1 + len2 + 2) / 2;
            return (findKthNumBetweenTwoArray(nums1, nums2, 0, 0, kth1) + findKthNumBetweenTwoArray(nums1, nums2, 0, 0, kth2)) / 2.0;
        }

        int findKthNumBetweenTwoArray(int[] nums1, int[] nums2, int l1, int l2, int kth)
        {
            int len1 = nums1.length - 1 - l1 + 1;
            int len2 = nums2.length - 1 - l2 + 1;
            if (len1 == 0)
            {
                return nums2[l2 + kth - 1];
            }
            else if (len2 == 0)
            {
                return nums1[l1 + kth - 1];
            }
            else if (kth == 1)
            {
                return Math.min(nums1[l1], nums2[l2]);
            }
            else
            {
                int h = kth / 2;
                int num1 = len1 >= h ? nums1[l1 + h - 1] : nums1[nums1.length - 1];
                int num2 = len2 >= h ? nums2[l2 + h - 1] : nums2[nums2.length - 1];
                int count;
                if (num1 < num2)
                {
                    count = Math.min(h, len1);
                    return findKthNumBetweenTwoArray(nums1, nums2, l1 + count, l2, kth - count);
                }
                else
                {
                    count = Math.min(h, len2);
                    return findKthNumBetweenTwoArray(nums1, nums2, l1, l2 + count, kth - count);
                }
            }
        }
    }
}
